Internet Info 1993/Internet Info CD-ROM (Walnut Creek) (1993).iso/answers/rec/puzzles/archive/series

Text File | 1993-08-18 | 16.8 KB | 540 lines

Newsgroups: rec.puzzles,news.answers,rec.answers
Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!spool.mu.edu!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!questrel!chris
From: [e-mail] (Chris Cole)
Subject: rec.puzzles Archive (series), part 34 of 35
Message-ID: <puzzles/archive/[e-mail]>
Followup-To: rec.puzzles
Summary: This is part of an archive of questions
 and answers that may be of interest to
 puzzle enthusiasts.
 Part 1 contains the index to the archive.
 Read the rec.puzzles FAQ for more information.
Sender: [e-mail] (Chris Cole)
Reply-To: [e-mail]
Organization: Questrel, Inc.
References: <puzzles/archive/[e-mail]>
Date: Wed, 18 Aug 1993 06:07:01 GMT
Approved: [e-mail]
Expires: Thu, 1 Sep 1994 06:04:11 GMT
Lines: 518
Xref: senator-bedfellow.mit.edu rec.puzzles:25021 news.answers:11541 rec.answers:1941

Archive-name: puzzles/archive/series
Last-modified: 17 Aug 1993
Version: 4


==> series/series.00.p <==
Are "complete this series" problems well defined?

==> series/series.00.s <==
Since there are infinitely many formulas that will fit any finite
series, many people object that such problems have no good answer.
But isn't this a special case of the general observation that theory
is underdetermined by experience (in other words, that there are a
lot of world views that are consistent with all the facts that we
know)?  And if so, doesn't this objection really apply to all puzzles?
Isn't it just more obvious in the case of series puzzles?

As a long-time observer of rec.puzzles nit-picking, I have never seen
a puzzle answer that could not be challenged.  The list of assumptions
made in solving any puzzle is neverending.  Luckily, most of us share
all or nearly all of these assumptions, so that we can agree on an
answer when we see it.

All of this has a lot to do with topics such as computational
complexity, algorithmic compressibility, Church's thesis, intelligence
and life.


==> series/series.01.p <==
M, N, B, D, P ?

==> series/series.01.s <==
T.  If you say the sounds these letters make out loud, you will see
that the next letter is T.  The letters are in the order of where the
sounds are formed in the mouth, from back to front.

==> series/series.02.p <==
H, H, L, B, B, C, N, O, F ?

==> series/series.02.s <==
Answer 1:  N, N, M, A  The first letters of the symbols for the elements.
Answer 2:  N, S, M, A  The first letters of the names of the elements.

==> series/series.03.p <==
W, A, J, M, M, A, J?

==> series/series.03.s <==
J, V, H, T, P, T, F, P, B, L.  Presidents of the US.

==> series/series.03a.p <==
G, J, T, J, J, J, A, M, W, J, J, Z, M, F, J, ?


==> series/series.03a.s <==
G, J, T, J, J, J, A, M, W, J, J, Z, M, F, J, A.  US Presidents' first names.

==> series/series.03b.p <==
A, J, B, C, G, T, C, V, J, T, D, F, K, B, H, ?


==> series/series.03b.s <==
A, J, B, C, G, T, C, V, J, T, D, F, K, B, H, J.  US Vice Presidents.

==> series/series.03c.p <==
M, A, M, D, E, L, R, H, ?


==> series/series.03c.s <==
M, A, M, D, E, L, R, H, A.  US Presidents' wives' first names.

==> series/series.04.p <==
A, E, H, I, K, L, ?

==> series/series.04.s <==
M, N, O, P, U, W.  Letters in the Hawaiian alphabet.

==> series/series.05.p <==
A B C D E F G H?

==> series/series.05.s <==
M.  The names of the cross-streets travelling west on (say)
Commonwealth Avenue from Boston's Public Garden: Arlington, Berkeley,
Clarendon, Dartmouth, Exeter, Fairfield, Gloucester, Hereford,
Massachusetts Ave.  The alphabet does continue in the Fenway; after
Massachuetts Ave., there is Charlesgate, and then Ipswich, Jersey,
Kilmarnock.

==> series/series.06.p <==
Z, O, T, T, F, F, S, S, E, N?

==> series/series.06.s <==
T.  The name of the integers starting with zero.

==> series/series.06a.p <==
F, S, T, F, F, S, ?

==> series/series.06a.s <==
The words "first", "second", "third", etc.  The same as the previous from this
point on.

==> series/series.07.p <==
1, 1 1, 2 1, 1 2 1 1, ...

What is the pattern and asymptotics of this series?

==> series/series.07.s <==
Each line is derived from the last by the transformation (for example)

... z z z x x y y y ... ->
... 3 z 2 x 3 y ...

John Horton Conway analyzed this in "The Weird and Wonderful Chemistry
of Audioactive Decay" (T M Cover & B Gopinath (eds) OPEN PROBLEMS IN
COMMUNICATION AND COMPUTATION, Springer-Verlag (1987)).  You can also
find his most complete FRACTRAN paper in this collection.

First, he points out that under this sequence, you frequently get
adjacent subsequences XY which cannot influence each other in any
future derivation of the sequence rule.  The smallest such are
called "atoms" or "elements".  As Conway claims to have proved,
there are 92 atoms which show up eventually in every sequence, no
matter what the starting value (besides <> and <22>), and always in
the same non-zero limiting proportions.

Conway named them after some other list of 92 atoms.  As a puzzle,
see if you can recreate the list from the following, in decreasing
atomic number:

U Pa Th Ac Ra Fr Rn Ho.AT Po Bi Pm.PB Tl Hg Au Pt Ir Os Re Ge.Ca.W Ta
HF.Pa.H.Ca.W Lu Yb Tm ER.Ca.Co HO.Pm Dy Tb Ho.GD EU.Ca.Co Sm PM.Ca.Zn
Nd Pr Ce LA.H.Ca.Co Ba Cs Xe I Ho.TE Eu.Ca.SB Pm.SN In Cd Ag Pd Rh
Ho.RU Eu.Ca.TC Mo Nb Er.ZR Y.H.Ca.Tc SR.U Rb Kr Br Se As GE.Na Ho.GA
Eu.Ca.Ac.H.Ca.ZN Cu Ni Zn.CO Fe Mn CR.Si V Ti Sc Ho.Pa.H.CA.Co K Ar
Cl S P Ho.SI Al Mg Pm.NA Ne F O N C B Be Ge.Ca.LI He Hf.Pa.H.Ca.Li

Uranium is 3, Protactinium is 13, etc.  Rn => Ho.AT means the following:
Radon forms a string that consists of two atoms, Holmium on the left,
and Astatine on the right.  I capitalize the symbol for At to remind
you that Astatine, and not Holmium, is one less than Radon in atomic
number.  As a check, against you or me making a mistake, Hf is 111xx,
Nd is 111xxx, In and Ni are 111xxxxx, K is 111x, and H is 22.

Next see if you can at least prove that any atom other than Hydrogen,
eventually (and always thereafter) forms strings containing all 92 atoms.

The grand Conway theorem here is that every string eventually forms (within
a universal time limit) strings containing all the 92 atoms in certain
specific non-zero limiting proportions, and that digits N greater than 3
are eventually restricted to one of two atomic patterns (ie, abc...N and
def...N for some {1,2,3} sequences abc... and def...), which Conway calls
isotopes of Np and Pu.  (For N=2, these are He and Li), and that these
transuranic atoms have a zero limiting proportion.

The longest lived exotic element is Methuselum (2233322211N) which takes
about 25 applications to reduce to the periodic table.

-Matthew P Wiener ([e-mail])

Conway gives many results on the ultimate behavior of strings under
this transformation: for example, taking the sequence derived from 1
(or any other string except 2 2), the limit of the ratio of length of
the (n+1)th term to the length of the nth term as n->infinity is a
fixed constant, namely

            1.30357726903429639125709911215255189073070250465940...

This number is from Ilan Vardi, "Computational Recreations in Mathematica",
Addison Wesley 1991, page 13.

Another sequence that is related but not nearly as interesting is:

1, 11, 21, 1112, 3112, 211213, 312213, 212223, 114213, 31121314, 41122314,
    31221324, 21322314,

and 21322314 generates itself, so we have a cycle.

==> series/series.08a.p <==
G, L, M, B, C, L, M, C, F, S, ?

==> series/series.08a.s <==
US Army officer ranks, descending.

==> series/series.08b.p <==
A, V, R, R, C, C, L, L, L, E, ?

==> series/series.08b.s <==
US Navy officer ranks, descending.

==> series/series.09a.p <==
S, M, S, S, S, C, P, P, P, ?

==> series/series.09a.s <==
Army non-comm ranks, descending.

==> series/series.09b.p <==
M, S, C, P, P, P, S, S, S, ?

==> series/series.09b.s <==
Navy non-comm ranks, descending.

==> series/series.10.p <==
D, P, N, G, C, M, M, S, ?

==> series/series.10.s <==
N, V, N, N, R.  US States in Constitution ratification order.

==> series/series.11.p <==
R O Y G B ?

==> series/series.11.s <==
V or I V.  Colors.

==> series/series.12.p <==
A, T, G, C, L, ?

==> series/series.12.s <==
V, L, S, S, C, A, P.  Zodiacal signs.

==> series/series.13.p <==
M, V, E, M, J, S, ?

==> series/series.13.s <==
U, N, P or U, P, N.  Names of the Planets.

==> series/series.14.p <==
A, B, D, O, P, ?

==> series/series.14.s <==
Q, R.  Only letters with an inside as printed.

==> series/series.14a.p <==
A, B, D, E, G, O, P, ?

==> series/series.14a.s <==
Q.  Letters with insides in cursive form.

==> series/series.15.p <==
A, E, F, H, I, ?

==> series/series.15.s <==
L, M, N, O, R, S, U, X.  Letters whose English names start with vowels.

==> series/series.16.p <==
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, X, Y?

==> series/series.16.s <==
Z.  Letters whose English names have one syllable.

==> series/series.17.p <==
T, P, O, F, O, F, N, T, S, F, T, F, E, N, S, N?

==> series/series.17.s <==
T, T, T, E, F, S.  Digits of Pi.

==> series/series.18.p <==
10, 11, 12, 13, 14, 15, 16, 17, 20, 22, 24, ___ , 100, 121, 10000

==> series/series.18.s <==
 10, 11, 12, 13, 14, 15, 16, 17, 20, 22, 24, 31 , 100, 121, 10000

Sixteen in base n for n=16, 15, ..., 2.

==> series/series.19.p <==
0 01 01011 0101101011011 0101101011011010110101101101011011 etc.

Each string is formed from the previous string by substituting '01' for '0'
and '011' for '1' simultaneously at each occurance.
Notice that each string is an initial substring of the previous string so
that we may consider them all as initial substrings of an infinite string.
The puzzle then is, given n, determine if the nth digit is 0 or 1 without
having to construct all the previous digits.  That is, give a non-recursive
formula for the nth digit.

==> series/series.19.s <==
Let G equal the limit string generated by the above process and define
the string F by

F[0] = "0",
F[n] = "1" if n = floor(phi*m) for some positive integer m,
F[n] = "0" if n = floor(phi^2*m) for some positive integer m,

where floor(x) is the greatest integer =< x and phi = (1 + \/5)/2;
I claim that F = G.


I will try to motivate my solution.  Let g[0]="0" and define g[n+1]
to be the string that results from replacing "0" in g[n] with "01"
and "1" with "011"; furthermore, let s(n) and t(n) be the number of
"0"'s and "1"'s in g[n], respectively.  Note that we have the
following recursive formulas : s(n+1) = s(n) + t(n) and t(n+1) =
s(n) + 2t(n).  I claim that s(n) = Fib(2n-1) and t(n) = Fib(2n),
where Fib(m) is the mth Fibonacci number (defined by Fib(-1) = 1,
Fib(0) = 0, Fib(n+1) = Fib(n) + Fib(n-1) for n>=0); this is easily
established by induction.  Now noting that Fib(2n)/Fib(2n-1) -> phi
as n -> infinity, we see that if the density of the "0"'s and "1"'s
exists, they must be be 1/phi^2 and 1/phi, respectively.  What is
the simplest generating sequence which has this property?  Answer:
the one given above.


Proof:  We start with

Beatty's Theorem: if a and b are positive irrational numbers such
that 1/a + 1/b = 1, then every positive integer has a representation
of the form floor(am) or floor(bm) (m a positive integer), and this
representation is unique.

This shows that F is well-defined.  I now claim that

Lemma: If S(n) and T(n) (yes, two more functions; apparently today's
the day that functions have their picnic) represent the number of
"0"'s and "1"'s in the initial string of F of length n, then S(n)
= ceil(n/phi^2) and T(n) = floor(n/phi) (ceil(x) is the smallest
integer >= x).

Proof of lemma: using the identity phi^2 = phi + 1 we see that S(n)
+ T(n) = n, hence for a given n either S(n) = S(n-1) + 1 or T(n) =
T(n-1) + 1.  Now note that if F[n-1]="1" ==> n-1 = floor(phi*m) for
some positive integer m and since phi*m-1 < floor(phi*m) < phi*m ==>
m-1/phi < (n-1)/phi < m ==> T(n) = T(n-1) + 1.   To finish, note that
if F[n-1]="0" ==> n-1 = floor(phi^2*m) for some positive integer m
and since phi^2*m-1 < floor(phi^2*m) < phi^2*m ==> m-1/phi^2 <
(n-1)/phi^2 < m ==> S(n) = S(n-1) + 1.  Q.E.D.

I will now show that F is invariant under the operation of replacing
"0" with "01" and "1" with "011"; it will then follow that F=G.
Note that this is equivalent to showing that F[2S(n) + 3T(n)]
= "0", F[2S(n) + 3T(n) + 1] = "1", and that if n = [phi*m] for some
positive integer m, then F[2S(n) + 3T(n) + 2] = "1".  One could
waste hours trying to prove some fiendish identities; watch how
I sidestep this trap.  For the first part, note that by the above
lemma F[2S(n) + 3T(n)] = F[2*ceil(n/phi^2) + 3*floor(n/phi)] =
F[2n + floor(n/phi)] = F[2n + floor(n*phi-n)] = F[floor(phi*n+n)]
= F[floor(phi^2*n)] ==> F[2S(n) + 3T(n)] = "0".  For the second, it
is easy to see that since phi^2>2, if F[m]="0" ==> F[m]="1" hence
the first part implies the second part.  Finally, note that if n =
[phi*m] for some positive integer m, then F[2S(n) + 3T(n) + 3] =
F[2S(n+1) + 3T(n+1)] = "0", hence by the same reasoning as above
F[2S(n) + 3T(n) + 2] = "1".

Q.E.D.

    -- [e-mail] (Chris Long)

==> series/series.20.p <==
1 2 5 16 64 312 1812 12288

==> series/series.20.s <==
ANSWER: 95616
    The sum of factorial(k)*factorial(n-k) for k=0,...,n.

==> series/series.21.p <==
5, 6, 5, 6, 5, 5, 7, 5, ?

==> series/series.21.s <==
The number of letters in the ordinal numbers.

First   5
Second  6
Third   5
Fourth  6
Fifth   5
Sixth   5
Seventh 7
Eighth  6
Ninth   5
etc.

==> series/series.22.p <==
3 1 1 0 3 7 5 5 2 ?

==> series/series.22.s <==
ANSWER: 4
    The digits of pi expressed in base eight.

==> series/series.23.p <==
22 22 30 13 13 16 16 28 28 11 ?

==> series/series.23.s <==
ANSWER: 15
    The birthdays of the Presidents of the United States.


==> series/series.24.p <==
What is the next letter in the sequence: W, I, T, N, L, I, T?

==> series/series.24.s <==
S.  First letters of words in question.

==> series/series.25.p <==
1 3 4 9 10 12 13 27 28 30 31 36 37 39 40 ?

==> series/series.25.s <==
1 3 4 9 10 12 13 27 28 30 31 36 37 39 40 ...
Positive integers in binary, treated as a base 3 number and converted
to decimal.

==> series/series.26.p <==
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 ?

==> series/series.26.s <==
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 ...
Positive integers in binary, for each 1 bit (not changed) flip the next bit.
This can also be phrased in reversing sequences of numbers.
More simply, just the integers in reflective-Gray-code order.

==> series/series.27.p <==
0 1 1 2 1 2 1 3 2 2 1 3 1 2 2 4 1 3 1 3 2 2 1 4 2 ?

==> series/series.27.s <==
2 3 3 1 3 1 5 2 2 2 4 1 2 2 4 1 3 1 3 3 2 1 5 2 3 2 3 1 4 2 4 2 2 1 ...

Number of factors in prime factorization of positive integers.

==> series/series.28.p <==
0 2 3 4 5 5 7 6 6 7 11 7 13 9 8 8 17 8 19 9 10 13 23 9 10 ?

==> series/series.28.s <==
15 9 11 29 10 31 10 14 19 12 10 37 21 16 11 41 12 43 15 11 25 47 11 14 12 ...

Sum of factors in prime factorization of positive integers.

==> series/series.29.p <==
1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 ?

==> series/series.29.s <==
1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 ...
The number of 1s in the binary expansion of the positive integers.

==> series/series.30.p <==
I I T Y W I M W Y B M A D

==> series/series.30.s <==
? (first letters of "If I tell you what it means will you buy me a drink?")

==> series/series.31.p <==
6 2 5 5 4 5 6 3 7

==> series/series.31.s <==
6. The number of segments on a standard calculator display it takes
to represent the digits starting with 0.
  _       _   _       _   _   _   _   _
 | |   |  _|  _| |_| |_  |_    | |_| |_|
 |_|   | |_   _|   |  _| |_|   | |_|  _|

==> series/series.32.p <==
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1

==> series/series.32.s <==
0 -> 1   01 -> 10   0110 -> 1001   01101001 ->  10010110
Recursively append the inverse.

This sequence is known as the Morse-Thue sequence.  It can be defined
non-recursively as the nth term is the mod 2 count of 1s in n written
in binary:
        0->0 1->1 10->1 11->0 100->1 101->0 110->0 111->1 etc.

Reference:
    Dekking, et. al., "Folds! I,II,III"
    The Mathematical Intelligencer, v4,#3,#4,#4.

==> series/series.33.p <==
2 12 360 75600

==> series/series.33.s <==
2         = 2^1
12        = 2^2 * 3^1
360       = 2^3 * 3^2 * 5^1
75600     = 2^4 * 3^3 * 5^2 * 7^1
174636000 = 2^5 * 3^4 * 5^3 * 7^2 * 11^1

==> series/series.34.p <==
3 5 4 4 3 5 5 4 3

==> series/series.34.s <==
The number of letters in the English words for the counting numbers.

==> series/series.35.p <==
1 2 3 2 1 2 3 4 2 1 2 3 4 2 2 3

==> series/series.35.s <==
The number of letters in the Roman numeral representation of the numbers.

==> series/series.36.p <==
ETIANMSURWDKGO

==> series/series.36.s <==
HVF and U with an umlaut.

The letters are sorted by their international Morse code representations:

E .
T -

I ..
A .-
N -.
M --

S ...
U ..-
etc.


==> series/series.37.p <==
10^3 10^9 10^27 10^2 0 4 8 3


==> series/series.37.s <==
10^3  = one thousAnd
10^9  = one Billion
10^27 = one oCtillion
10^2  = one hunDreD
0     = zEro
4     = Four
8     = eiGht
3     = tHree
5     = fIve